package 强化训练;

public class day29正数数组中最小不能组成和 {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        System.out.println();
        System.out.println(getFirstUnFormedNum(arr));
    }

    /**
     * z找到数组中最小不能组成和
     */
    public static int getFirstUnFormedNum(int[] arr) {
        //min最小值，max最大和
        int min = arr[0];
        int max = 0;
        for (int i : arr) {
            max += i;
            min = Math.min(min,i);
        }
        //状态容器
        boolean[] res = new boolean[max+1];
        res[0] = true;//将0置为true，如果j = 当前数组中的数，那么j-arr[i] == 0 ，j就置为true = arr[0]
        for (int i : arr) {
            //以数组中的每一个元素为起点，从最大值开始遍历，
            for (int j = max; j >= i ; j--) {
                //当前位置的值=j-i位置的值 或上  j本身的值
                res[j] = res[j - i] || res[j];
            }
        }
        //最后开始遍历，找到第一个fasle返回
        for (int i = min; i < max+1; i++) {
            if (!res[i]){
                return i;
            }
        }
        //否则返回max+1；
        return max+1;

    }
}
